package sort;

/**
 * 直接插入排序
 * 
 * @author mengxin
 * 
 */
public class StraightInsertionSort {
	private int[] arr;

	public StraightInsertionSort(int[] arr) {
		this.arr = arr;
	}

	// 插入排序法
	public void sort() {
		for (int i = 1; i < arr.length; i++) {
			int insertVal = arr[i];
			// insertValue准备和前一个数比较
			int index = i - 1;

			while (index >= 0 && insertVal < arr[index]) {
				// 将把arr[index]向后移动
				arr[index + 1] = arr[index];
				// 让index向前移动一位
				index--;
			}

			// 将insertValue插入到适当位置
			arr[index + 1] = insertVal;
			System.out.println(this.toString());
		}
	}

	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "  ");
		}
		return sb.toString();
	}

	public static void main(String[] args) {
		StraightInsertionSort is = new StraightInsertionSort(new int[] { 1, 3,
				5, 7, 9, 2, 4, 6, 8, 0 });
		is.sort();
		System.out.println(is.toString());
	}
}
